'''
Created on Jul 31, 2012

@author: levilucio

graphs.py

'''
#import general_exceptions
import graphs_exceptions


class TG(object):
    """ Class Typed Graph"""

    def __init__(self, V, E):
        """ build a graph from a list of tuples representing edges """
        self.V = V
        self.E = set(E)
        if not self.__check_all_edge_vertex_defined(): raise graphs_exceptions.NotAllEdgeVertexDefined      
    
    def union(self, tg):
        """ Typed graph union. Non-Disjoint """
        self.V.update(tg.V)
        self.E = self.E.union(tg.E)

    def get_next_edges(self, e):
        """ get the set of edges that follow a directed edge """
        next_edges = []
        for ee in self.E:
            if e[1] == ee[0]:
                next_edges.append(ee)
        return next_edges

    def get_previous_edges(self, e):
        """ get the set of edges that precede a directed edge """
        previous_edges = {}
        for ee in self.E:
            if e[0] == ee[1]:
                previous_edges.add(ee)
        return previous_edges
    
    def get_edge_starting_with_vertex(self, v):
        """ get the directed edge having 'v' as its start """
        for e in self.E:
            if e[0] == v: return e
        return False
    
    def get_edge_ending_with_vertex(self, v):
        """ get the directed edge having 'v' as its end """
        for e in self.E:
            if e[1] == v: return e
        return False
        
    def __check_all_edge_vertex_defined(self):
        """ check if all vertices in edges are defined in V """
        vnames = set(self.V.keys()) 
        for e in self.E:
            if not (e[0] in vnames and e[1] in vnames): 
                return False
        return True    

    def printargs(self):
        """ Method docstring. """
        print "Typed graph"
        print self.V
        print self.E
        
    def export_dot(self, filehandle):
        for e in self.E:
            filehandle.write('   ' + e[0] + '_' + self.V[e[0]] + ' -> ' + e[1] + '_' + self.V[e[1]] + ';\n')        
                
            
class ITG(TG):
    """ Class Indirect Typed Graph """    

    def __init__(self, V, E, Il):
        """ build an indirect typed graph from a list of tuples representing edges and a set of indirect edges """        
        super(ITG, self).__init__(V, E)
        self.Il = set(Il)
#        if not self.__check_indirect_in_edges(): raise graph_exceptions.NotIndirectEdgesInTypedGraphEdges
        if not self.__check_indirect_links(): raise graphs_exceptions.ImpossibleIndirectEdges

    def union(self, itg):
        """ Indirect typed graph union. Non-Disjoint """                
        super(ITG, self).union(itg)
        self.Il = self.Il.union(itg.Il)
        
    def __check_indirect_links(self):
        """ ckeck if all the indirect links are part of the transitive closure of the regular edges in the graph """
        for ile in self.Il:
            if not self.__check_reach_transitive(self.get_edge_starting_with_vertex(ile[0]), ile[1]): return False
        return True
        
    def __check_reach_transitive(self, e, last):
        """ check if it is possible to reach a vertex transitively. Recursive """  
        if (e[1] == last): return True
        else:
            next_edge_list = self.get_next_edges(e)
            if not next_edge_list : return False
            else:
                result = False
                for e in next_edge_list: 
                    if (e[2] == 'containment'): 
                        result = result or self.__check_reach_transitive(e, last)
                return result        
    
    # do I need this ???
#    def __check_indirect_in_edges(self):
#        """ Check if all the indirect edges are contained in the graph's edges """
#        if self.Il.issubset(self.E): return True
#        else: return False
        
    def printargs(self):
        """ Method docstring. """
        print "Indirect typed graph"
        super(ITG, self).printargs()        
        print self.Il

    def export_dot(self, filehandle):
        super(ITG, self).export_dot(filehandle)
        for e in self.Il:
            filehandle.write('   ' + e[0] + '_' + self.V[e[0]] + ' -> ' + e[1] + '_' + self.V[e[1]] + ' [style=dotted];\n') 
